/*
138. 复制带随机指针的链表
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的 深拷贝。

常规思路: 用一个map存储每个节点(key)和对应的拷贝节点(value), 方便，但是额外空间为O(n)
最优思路:
  原链表: 1 -> 2 -> 3 -> null
  复制链表的next: 1 -> 1' -> 2 -> 2' -> 3 -> 3' ->null
  然后处理节点的random指针
 */

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */
/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function (head) {
  if (!head) {
    return null
  }
  let cur = head
  // 先处理next
  while (cur) {
    const next = cur.next
    const newNode = new Node(cur.val, null, null)
    cur.next = newNode
    newNode.next = next
    cur = next
  }
  // 处理random
  cur = head
  while (cur) {
    const originalNode = cur.random
    cur.next.random = originalNode ? originalNode.next : null // 万一originalNode是null，则没法next
    cur = cur.next.next
  }
  // split
  const copyHead = head.next
  cur = head
  while (cur) {
    const copyNode = cur.next
    cur.next = copyNode.next
    copyNode.next = cur.next ? cur.next.next : null // 由于最后的null不会复制一份，因此区别对待
    cur = cur.next
  }
  return copyHead
}
